package com.example.algorithmdemo.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class TestBTree {
    /**
     * 测试二叉树的功能
     */
    public static void testBTreeFunctions(){
        BTreeNode treeNode = new BTreeNode(1);
        treeNode.left = new BTreeNode(2);
        treeNode.right = new BTreeNode(3);
        treeNode.left.left = new BTreeNode(4);
        treeNode.left.right = new BTreeNode(5);
        treeNode.right.left = new BTreeNode(6);
        treeNode.right.right = new BTreeNode(7);

        preOrderRecursive(treeNode);

        //求二叉树的最大深度
       int maxDepth_result  = maxDepth(treeNode);
       System.out.println("maxDepth_result:" + maxDepth_result);

       //合并二叉树
       BTreeNode mergeNewTree = mergeTrees(treeNode,treeNode);
       //前序输出合并后的二叉树
        preOrderRecursive(mergeNewTree);

        //二叉搜索树
        BTreeNode bTreeNode = new BTreeNode(3);
        bTreeNode.left = new BTreeNode(1);
        bTreeNode.right = new BTreeNode(5);//2则不是
        boolean isResult = isValidBST(bTreeNode);
        System.out.println("isResult:" + isResult);
    }

    /**
     * 判断是否为二叉搜索树
     * 利用中序遍历后为升序结果，非升序则不是二叉搜索树
     * @param treeNode
     * @return
     */
    private static boolean isValidBST(BTreeNode treeNode){
        List<Integer> integerList = new ArrayList<>();
        middleForEach(integerList,treeNode);
        for (int i = 1; i < integerList.size(); i++) {
            if (integerList.get(i-1) > integerList.get(i)){
                return false;
            }
        }
        return true;
    }
    private static void middleForEach(List<Integer>list,BTreeNode treeNode){
        middleForEach(list,treeNode.left);
        list.add(treeNode.value);
        middleForEach(list, treeNode.right);
    }
    /**
     * 合并二叉树
     * @param t1
     * @param t2
     * @return
     */
    private static BTreeNode mergeTrees(BTreeNode t1,BTreeNode t2){
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        BTreeNode mergeNode = new BTreeNode(t1.value + t2.value);
        mergeNode.left = mergeTrees(t1.left,t2.left);
        mergeNode.right = mergeTrees(t1.right,t2.right);
        return  mergeNode;
    }

    /**
     * 求二叉树的最大深度
     * @param treeNode
     * @return
     */
    private static int maxDepth(BTreeNode treeNode){
        if (treeNode == null) return 0;
        int leftMax = maxDepth(treeNode.left);
        int rightMax = maxDepth(treeNode.right);
        return Math.max(leftMax,rightMax) + 1;
    }
    /**
     * 递归实现先序遍历
     * @param treeNode
     */
    private static void preOrderRecursive(BTreeNode treeNode){
        if (treeNode != null){
            System.out.println("递归实现先序遍历=" + treeNode.value);
            preOrderRecursive(treeNode.left);
            preOrderRecursive(treeNode.right);
        }
    }

    /**
     * 非递归实现二叉树变量
     * @param treeNode
     */
    private static void preOrderUnRecursive(BTreeNode treeNode){
        if (treeNode != null){
            Stack<BTreeNode> treeNodes = new Stack<>();
            treeNodes.push(treeNode);
            while (!treeNodes.isEmpty()){
                BTreeNode head = treeNodes.pop();
                System.out.println("非递归实现先序遍历=" + head.value);
                if (head.right != null){
                    treeNodes.push(head.right);
                }
                if (head.left != null){
                    treeNodes.push(head.left);
                }
            }
        }
    }

    /**
     * 递归实现中序遍历
     * @param treeNode
     */
    private static void midOrderRecursive(BTreeNode treeNode){
        if (treeNode != null){
            midOrderRecursive(treeNode.left);
            System.out.println("递归实现中序遍历" + treeNode.value);
            midOrderRecursive(treeNode.right);
        }
    }
}
